package com.fe.class07;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @Description 最大线段重合问题
 * 给定很多线段，每个线段都有两个数[start, end]， 表示线段开始位置和结束位置，左右都是闭区间 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 * @Author sosuke :-)
 * @Date 2022/1/3 09:46
 */
public class Code01_CoverLineMax {
    // 重合区域的左边界必是某个线段的左边界
    // 对每个线段，求以线段左边界开始的重合区域包含几条线段，最后所有线段算出的最大值即为结果

    /**
     * 1. 把所有线段按照开始位置从小到大排序，准备一个小根堆，用于存储线段的结束位置
     * 2. 对于每个线段，将小根堆中 <= 线段开始位置的值都弹出（表示不会和当前线段有重合）
     * 把线段的结束位置加入小根堆，此时小根堆中有多少个数就表示这个线段包含几个重合区域
     * 3. 所有线段计算的值的最大值，即为结果
     */
    // 线段数组：[{0,3}, {1,5}, ...]
    // O(N*logN)，所有线段入堆一次，出堆一次
    public static int maxCover(int[][] lines) {
        // 将int[][] lines转换成Line数组
        Line[] linesArr = new Line[lines.length];
        for (int i = 0; i < lines.length; i++) {
            linesArr[i] = new Line(lines[i][0], lines[i][1]);
        }
        // 1. 按照线段开始位置排序
        Arrays.sort(linesArr, (a, b) -> a.start - b.start);

        int ans = 0;
        // 小根堆，用于存储线段的结束位置
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // 2. 遍历所有线段
        for (int i = 0; i < linesArr.length; i++) {
            // 将小根堆中 <= 线段开始位置的值都弹出
            while (!heap.isEmpty() && heap.peek() <= linesArr[i].start) {
                heap.poll();
            }
            // 把线段的结束位置加入小根堆
            heap.add(linesArr[i].end);
            ans = Math.max(ans, heap.size());
        }
        return ans;
    }

    public static class Line {
        public int start;
        public int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    // 第二种方法用于测试
    public static int testMaxCover(int[][] lines) {
        int min = Integer.MAX_VALUE;//表示所有线段开始值的最小值
        int max = Integer.MIN_VALUE;//表示所有线段结束值的最大值
        for (int i = 0; i < lines.length; i++) {
            min = Math.min(min, lines[i][0]);
            max = Math.max(max, lines[i][1]);
        }

        int ans = 0;
        for (double p = min + 0.5; p < max; p++) {
            // 对于一个p来说，求有多少线段包含它
            int value = 0;
            for (int i = 0; i < lines.length; i++) {
                if (lines[i][0] < p && lines[i][1] > p) {
                    value++;
                }
            }
            ans = Math.max(ans, value);
        }
        return ans;
    }

    public static void main(String[] args) {
        int testTimes = 200000;
        int maxSize = 5; // 线段最大个数
        int start = 0; // 线段最小开始位置
        int end = 200; // 线段最大结束位置
        for (int i = 0; i < testTimes; i++) {
            int[][] lines = generateLines(maxSize, start, end);
            int ans1 = maxCover(lines);
            int ans2 = testMaxCover(lines);
            if (ans1 != ans2) {
                System.out.println("Fuck");
                System.out.println("lines = " + printArr(lines));
                System.out.println("ans1 = " + ans1);
                System.out.println("ans2 = " + ans2);
                return;
            }
        }
        System.out.println("Nice");
        int[][] lines = generateLines(maxSize, start, end);
        System.out.println(printArr(lines));
        System.out.println("maxCover(lines) = " + maxCover(lines));
    }

    // 随机生成线段数组（二维数组）
    private static int[][] generateLines(int maxSize, int L, int R) {
        int size = (int) (Math.random() * maxSize) + 1;
        int[][] ans = new int[size][2]; // 用二维数组表示线段数组，每个线段有两个数
        for (int i = 0; i < size; i++) {
            int a = L + (int) (Math.random() * (R - L + 1));
            int b = L + (int) (Math.random() * (R - L + 1));
            if (a == b) { // 线段长度>=1
                b = a + 1;
            }
            ans[i][0] = Math.min(a, b);
            ans[i][1] = Math.max(a, b);
        }
        return ans;
    }

    // 打印线段数组(二维数组)
    private static String printArr(int[][] lines) {
        String[] lineArr = new String[lines.length];
        for (int i = 0; i < lines.length; i++) {
            StringBuffer line = new StringBuffer("{");
            int start = lines[i][0];
            int end = lines[i][1];
            line.append(start).append(",").append(end).append("}");
            lineArr[i] = line.toString();
        }

        return Arrays.toString(lineArr);
    }
}
